package 二叉树相关问题.层次遍历;

import java.util.*;

public class 打家劫舍3 {

    public int rob(TreeNode root) {
        List<List<Integer>> lists = new LinkedList<>();
        Queue<TreeNode> q=new LinkedList();
        int max1=0;
        int max2=0;
        if (root==null)
            return 0;
        if (root.left==null && root.right==null)
            return root.val;
        q.offer(root);
        while (!q.isEmpty()){
            List<Integer> list = new LinkedList<>();
            for (int i = q.size(); i>0 ; i--) {
                TreeNode poll = q.poll();
                list.add(poll.val);
                if(poll.left!=null)
                    q.offer(poll.left);
                if (poll.right!=null)
                    q.offer(poll.right);
            }
            lists.add(new ArrayList<>(list));
        }
        int[] nums = new int[lists.size()];
        for (int i = 0; i < lists.size(); i++) {
            int sum=0;
            List<Integer> list = lists.get(i);
            for (int j = 0; j < list.size(); j++) {
                sum+=list.get(i);
            }
            nums[i]=sum;
        }
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]+" ");
        }
        int n=nums.length;
        int[] dp = new int[n + 1];
        dp[1]=nums[0];
        for (int i = 2; i < n+1; i++) {
            dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i-1]);
        }
        return dp[n];
    }
}
